Utilizing the multiple facets of WWW contents

Current query languages for the Web (e.g., W3QL, WebLog and WebSQL) explore the structure of the Web. However, usually, the structure of the Web has little to do with the semantics of the data. Therefore, it is practically difficult to pose database queries over the Web. We introduce a new type of tags for denoting the semantics of data stored in HTML pages. These semantic tags (implemented as HTML comments) superimpose on HTML pages semistructured objects in the style of the OEM model. The paper discusses two implemented tools for fully utilizing the semantics. The first is a visualization tool for displaying both the HTML reading of Web pages and the OEM reading of Web pages. The second tool is a query language, similar to LOREL, that can query the HTML structure and/or the OEM reading. The above formalism and tools provide data-modeling capabilities for the Web that fit its heterogeneous nature. Real database queries, taking the OEM point of view, can be formulated, including queries about the schema as well as queries about the HTML structure of Web pages. Therefore, the query language is not restricted to portions of the Web in which semantic tags are used.     

On-line restricted assignment of temporary tasks with unknown durations

We consider load balancing of temporary tasks on m machines in the restricted assignment model. It is known that the best competitive ratio for this problem is . This bound is not achieved by the greedy algorithm whose competitive ratio is known to be Ω(m2/3). We give an alternative analysis to the greedy algorithm which is better than the known analysis for relatively small values of m. We also show that for a small number of machines, namely m?5, the greedy algorithm is optimal.     

Membrane fluctuations around inclusions

The free energy of inserting a protein into a membrane is determined by considering the variation in the spectrum of thermal fluctuations in response to the presence of a rigid inclusion. Both numerically and through a simple analytical approximation, we find that the primary effect of fluctuations is to reduce the effective surface tension, hampering the insertion at low surface tension. Our results, which should also be relevant for membrane pores, suggest (in contrast to classical nucleation theory) that a finite surface tension is necessary to facilitate the opening of a pore.     

Repositioning of distinguishable urban service units on networks

This paper examines the problem of repositioning mobile emergency service units on the urban Transportation network. Repositioning problems deal with real-time movements of available servers to better anticipate short-term future requests for service. It is assumed in the paper that q nodes of the network are designated as “home locations” for q distinguishable units. Depending on the status of other servers (busy or available), any particular available server can be moved to other locations (not necessarily home locations) in the network. Using Markovian Decision Theory, the policy space consists of decisions on where and when to move servers for any possible state. The paper includes an analysis of two cases based on the quality of information on the real-time location of non-stationary service units. In one case the assumption is that the dispatcher has perfect information whereas that in the other one it is assumed that no such information is available. The objective is to find the repositioning policy which minimizes the expected cost of operating the system in the long term.     

Tuning energetic levels in nanocrystal quantum dots through surface manipulations

We demonstrate tuning of the electronic level positions with respect to the vacuum level in colloidal InAs nanocrystals using surface ligand exchange. Electrochemical as well as scanning tunneling spectroscopy measurements reveal that the tuning is largely dependent on the nanocrystal size and the surface linking group, while the polarity of the ligand molecules has a lesser effect. The implications of affecting the electronic system of nanocrystal through its capping are illustrated through prototype devices.     

Space Complexity Vs. Query Complexity

Combinatorial property testing deals with the following relaxation of decision problems: Given a fixed property and an input x, one wants to decide whether x satisfies the property or is “far” from satisfying it. The main focus of property testing is in identifying large families of properties that can be tested with a certain number of queries to the input. In this paper we study the relation between the space complexity of a language and its query complexity. Our main result is that for any space complexity s(n) ≤ log n there is a language with space complexity O(s(n)) and query complexity 2^Ω(s(n)). Our result has implications with respect to testing languages accepted by certain restricted machines. Alon et al. [FOCS 1999] have shown that any regular language is testable with a constant number of queries. It is well known that any language in space o(log log n) is regular, thus implying that such languages can be so tested. It was previously known that there are languages in space O(log n) that are not testable with a constant number of queries and Newman [FOCS 2000] raised the question of closing the exponential gap between these two results. A special case of our main result resolves this problem as it implies that there is a language in space O(log log n) that is not testable with a constant number of queries. It was also previously known that the class of testable properties cannot be extended to all context-free languages. We further show that one cannot even extend the family of testable languages to the class of languages accepted by single counter machines.      

Experiential learning approach for requirements engineering education

The use of requirements engineering (RE) in industry is hampered by a poor understanding of its practices and their benefits. Teaching RE at the university level is therefore an important endeavor. Shortly before students become engineers and enter the workforce, this education could ideally be provided as an integrated part of developing the requisite business skills for understanding RE. Because much social wisdom is packed into RE methods, it is unrealistic to expect students with little organizational experience to understand and appreciate this body of knowledge; hence, the necessity of an experiential approach. The course described in this paper uses an active, affective, experiential pedagogy giving students the opportunity to experience a simulated work environment that demonstrates the social/design–problem complexities and richness of a development organization in the throes of creating a new product. Emotional and technical debriefing is conducted after each meaningful experience so that students and faculty, alike can better understand the professional relevancies of what they have just experienced. This includes an examination of the many forces encountered in industrial settings but not normally discussed in academic settings. The course uses a low-tech social simulation, rather than software simulation, so that students learn through interaction with real people, and are therefore confronted with the complexity of true social relationships.     

The tensor product of two good codes is not necessarily robustly testable

Given two codes R and C, their tensor product $R?C$ consists of all matrices whose rows are codewords of R and whose columns are codewords of C. The product $R?C$ is said to be robust if for every matrix M that is far from $R?C$ it holds that the rows and columns of M are far on average from R and C respectively. Ben-Sasson and Sudan (RSA 28(4), 2006) have asked under which conditions the product $R?C$ is robust.Addressing this question, Paul Valiant (APPROX-RANDOM 2005) constructed two linear codes with constant relative distance whose tensor product is not robust. However, one of those codes has a sub-constant rate. We show that this construction can be modified such that both codes have both constant rate and constant relative distance. We also provide an alternative proof for the non-robustness of the tensor product of those codes, based on the inverse direction of the “rectangle method” that was presented by the second author (ECCC TR07-061). We believe that this proof gives an additional intuition for why this construction works.     

Living in a bubble? Toward a unified bubble theory

We generalise the notion of a bubble beyond the financial domain, by showing how a single social mechanism, based on an information feedback-loop, explains both financial bubbles and other seemingly disparate social phenomena, such as the recognition of academic articles, website popularity, and the spread of rumours.

We discuss examples of phenomena explained by this bubble mechanism, as well as other phenomena that exhibit certain bubble characteristics, yet are not bubbles according to our model. Finally, we present mathematical mechanisms for two phenomena that conform with our model, and show by computer simulation how they exhibit bubble behaviour.